Bajtonowiec [B]

Limit pamięci: 128 MB

Bajtonowiec to drzewo, na którym rosną bajtony. Są to rzadkie owoce i można je znaleźć tylko na takich gałęziach, z których nie wyrastają żadne inne gałęzie.

Wszystkie bajtony rosnące na danej gałęzi mają wyznaczony przedział czasu, w którym mogą zostać zebrane. Jeśli zostaną zebrane zbyt wcześnie, będą niedojrzałe, a jeśli za późno - będą zgniłe. Każdy właściciel bajtonowca zastanawia się, ile minimalnie cięć musi wykonać, aby zebrać wszystkie bajtony oraz aby każdy zebrany bajton nadawał się do zjedzenia w chwili zebrania. Cięcia można wykonywać na każdej gałęzi, u jej początku. W momencie ścięcia zebrane zostają wszystkie bajtony rosnące bezpośrednio lub pośrednio na ścinanej gałęzi. Zakładamy, że w jednostce czasu można wykonać dowolną liczbę cięć oraz że pień również jest gałęzią.

Wejście

Pierwszy i jedyny wiersz standardowego wejścia zawiera opis bajtonowca, podany w postaci rekurencyjnej. Pierwsza liczba oznacza liczbę gałęzi wychodzących z pnia, następnie znajdują się opisy tych gałęzi. Opis gałęzi składa się z liczby wychodzących z niej gałęzi, a następnie opisu tych gałęzi. Jeśli na gałęzi rosną bajtony, to liczba wychodzących gałęzi jest równa zeru, a następnie podane są dwie liczby całkowite , (), oznaczające przedział czasu, w którym można zebrać dane bajtony. Liczba wszystkich gałęzi nie przekracza .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą równą minimalnej liczbie cięć, jakie należy wykonać, aby wszystkie bajtony nadawały się do zjedzenia.

Przykład

Dla danych wejściowych:

2 1 0 3 5 2 0 8 10 1 0 6 9

poprawną odpowiedzią jest:

2

Wyjaśnienie do przykładu: Przykładowy bajtonowiec ma trzy gałęzie, na których rosną bajtony - przedziały na rysunku to okresy ich zdatności do spożycia. Aby zebrać wszystkie bajtony, wystarczą w tym przypadku dwa cięcia: jedno z nich można wykonać na przykład w chwili 5, a drugie w chwili 8.

Autor zadania: Jacek Tomasiewicz.